#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mem(x) memset(x,0,sizeof(x))
#define endl "\n"
#define printYes cout << "Yes\n"
#define printYES cout << "YES\n"
#define printNo cout << "No\n"
#define printNO cout << "NO\n"
#define lowbit(x) ((x)&(-(x)))
#define pb push_back
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,j,k) for (int i=(j);i<=(k);i++)
#define per(i,j,k) for (int i=(j);i>=(k);i--)
#define pcnt(x) __builtin_popcount(x)
mt19937 rnd(time(0));
template<class T>void chkmin(T&x,T y){x=min(x,y);}
template<class T>void chkmax(T&x,T y){x=max(x,y);}

const ll inf=1000000000000000000; 
//const ll inf=1000000000;
//const ll mod=998244353;
//const ll mod=1000000007;

const int N=1000005;
int n,m,q; 
ll a[N],c[N],b[N],d[N];
void solve(int l,int r)
{
	c[l-1]=0,c[r+1]=0;
	rep(i,l,r) c[i]=a[i];
	rep(i,l,r+1) b[i]=c[i]-c[i-1],d[i]=0;
	ll dt=0,res=0;
	rep(i,l,r)
	{
		ll p=min(d[i],dt);
		dt-=p,d[i]-=p;
		ll z=b[i]+d[i];
		if (z>=0)
		{
			res+=z;
			d[min(i+m,r+1)]+=z;
		}
		else if (z<=0)
		{
			dt-=z;
		}
	} 
	cout << res << endl;
}

int main()
{
	freopen("clear.in","r",stdin);
	freopen("clear.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> q;
	rep(i,1,n) cin >> a[i];
	rep(i,1,q)
	{
		int l,r;
		cin >> l >> r;
		solve(l,r);
	}
	return 0;
}
